using System;
using UnityEngine;
using System.Collections.Generic;
using System.Linq;

namespace DanielSig.UnityExtensions
{
	public class VertexPoint
	{
		public Vector3 Position;
		public Vector3 Normal;
		public Vector4 Tangent;
		public Vector2 UV;
	}
	public static class XMesh2
	{
		private const float _FIX_SEAM_AMOUNT = 0.001F;
		
		public static void ModifyShapeFast(this Mesh m, Func<Vector3, Vector3> func)
		{
			LinkedList<Triangle> triangles = new LinkedList<Triangle>();
			RelayModifyShapeFast(Import(triangles, m), func);
			Export(triangles, m);
		}
		public static void ModifyShape(this Mesh m, Func<VertexPoint, Vector3> func)
		{
			LinkedList<Triangle> triangles = new LinkedList<Triangle>();
			RelayModifyShape(Import(triangles, m), func);
			Export(triangles, m);
		}
		public static void Modify(this Mesh m, Action<VertexPoint> func)
		{
			LinkedList<Triangle> triangles = new LinkedList<Triangle>();
			Import(triangles, m);
			RelayModify(triangles, func);
			Export(triangles, m);
		}
		public static void Optimize(this Mesh m, float amount, int iterations, bool convex)
		{
			iterations.ClampBetween(1, 20);
			float step = amount / iterations;
			amount = step;
			for(int i = 0; i < iterations; i++)
			{
				LinkedList<Triangle> triangles = new LinkedList<Triangle>();
				Reduce(Import(triangles, m), amount.Clamp(), convex);
				Export(triangles, m);
				amount += step;
			}
		}
		
		private class Point
		{
			private static readonly Dictionary<Vector3, Point> _points = new Dictionary<Vector3, Point>();
			
			public Vector3 Position;
			private bool _visited = false;
			private readonly LinkedList<Link> _links = new LinkedList<Link>();
			
			public static void Init()
			{
				_points.Clear();
			}
			
			public static Point RequesPoint(Vector3 pos)
			{
				foreach (KeyValuePair<Vector3, Point> pair in _points)
				{
					if(pair.Key.DistanceToSqr(pos) < _FIX_SEAM_AMOUNT)
					{
						return pair.Value;
					}
				}
				Point newPoint = new Point(pos);
				_points.Add(pos, newPoint);
				return newPoint;
			}
			
			private Point(Vector3 pos)
			{
				Position = pos;
			}
			public void ForEachLink(Action<Link> action)
			{
				foreach(Link link in _links)
				{
					action(link);
				}
			}
			public Link AnyLink
			{
				get
				{
					return _links.Count > 0 ? _links.First.Value : null;
				}
			}
			public Link RequestLink(Vector2 uv, Vector3 normal, Vector4 tangent)
			{
				foreach(Link link in _links)
				{
					if(link.UV == uv && link.Normal == normal && link.Tangent == tangent) return link;
				}
				Link newLink = new Link(uv, normal, tangent, this);
				_links.AddLast(newLink);
				return newLink;
			}
			public bool HasBeenVisited
			{
				get
				{
					bool temp = _visited;
					_visited = true;
					return temp;
				}
			}
			public void CollapseWith(Point p)
			{
				foreach (Link link in _links)
				{
					//Vector2 uv = link.UV;
					Vector3 normal = link.Normal;
					//Link other = p._links.Aggregate(p._links.First.Value, (best, x) => x.UV.DistanceToSqr(uv) < best.UV.DistanceToSqr(uv) ? x : best);
					Link other = p._links.Aggregate(p._links.First.Value, (best, x) => x.Normal.Dot(normal) > best.Normal.Dot(normal) ? x : best);
					link.CollapseWith(other);
				}
			}
		}
		private class Link
		{
			public Vector2 UV;
			public Vector3 Normal;
			public Vector4 Tangent;
			public readonly Point Point;
			public readonly LinkedList<Triangle> Triangles = new LinkedList<Triangle>();
			
			private bool _visited = false;
			public bool HasBeenVisited
			{
				get
				{
					bool temp = _visited;
					_visited = true;
					return temp;
				}
			}
			private int _index = -1;
			public bool HasBeenIndexed
			{
				get
				{
					return _index >= 0;
				}
			}
			public int Index
			{
				get
				{
					if(_index < 0) throw new InvalidOperationException("Index has not been assigned yet");
					return _index;
				}
				set
				{
					if(_index >= 0) throw new InvalidOperationException("Index has already been assigned");
					_index = value;
				}
			}
			
			public Link(Vector2 uv, Vector3 normal, Vector4 tangent, Point point)
			{
				UV = uv;
				Normal = normal;
				Tangent = tangent;
				Point = point;
			}
			
			public void CollapseWith(Link other)
			{
				while(Triangles.Count > 0)
				{
					Triangles.First.Value.ResetLink(this, other);
				}
			}
			public static explicit operator VertexPoint(Link link)
			{
				return new VertexPoint{ Position = link.Point.Position, Normal = link.Normal, Tangent = link.Tangent, UV = link.UV };
			}
			public void Apply(VertexPoint vp)
			{
				UV = vp.UV;
				Normal = vp.Normal;
				Tangent = vp.Tangent;
				if(Point.Position != vp.Position && !Point.HasBeenVisited) Point.Position = vp.Position;
			}
			public void Modify(Action<VertexPoint> mod)
			{
				VertexPoint vp = (VertexPoint)this;
				mod(vp);
				Apply(vp);
			}
		}
		private class Triangle
		{
			private Link _link1;
			private Link _link2;
			private Link _link3;
			private readonly LinkedListNode<Triangle> _thisLinkedListNode;
			
			public Link Link1
			{
				get{ return _link1; }
				set
				{
					if(value == null) return;
					
					if(_link1 != null) _link1.Triangles.Remove(this);
					_link1 = value;
					_link1.Triangles.AddLast(this);
					CheckIfCollapsed();
				}
			}
			public Link Link2
			{
				get{ return _link2; }
				set
				{
					if(value == null) return;
					
					if(_link2 != null) _link2.Triangles.Remove(this);
					_link2 = value;
					_link2.Triangles.AddLast(this);
					CheckIfCollapsed();
				}
			}
			public Link Link3
			{
				get{ return _link3; }
				set
				{
					if(value == null) return;
					
					if(_link3 != null) _link3.Triangles.Remove(this);
					_link3 = value;
					_link3.Triangles.AddLast(this);
					CheckIfCollapsed();
				}
			}
			public LinkedList<Link> Links
			{
				get
				{
					LinkedList<Link> links = new LinkedList<Link>();
					links.AddLast(Link1);
					links.AddLast(Link2);
					links.AddLast(Link3);
					return links;
				}
			}
			
			public Triangle(Link link1, Link link2, Link link3, LinkedList<Triangle> triangles)
			{
				_thisLinkedListNode = triangles.AddLast(this);
				Link1 = link1;
				Link2 = link2;
				Link3 = link3;
			}
			private void CheckIfCollapsed()
			{
				if(_link1 == null || _link2 == null || _link3 == null) return;
				
				if(_link1.Point == _link2.Point || _link1.Point == _link3.Point || _link2.Point == _link3.Point)
				{
					 _link1.Triangles.Remove(this);
					 _link2.Triangles.Remove(this);
					 _link3.Triangles.Remove(this);
					_thisLinkedListNode.List.Remove(_thisLinkedListNode);
					 _link1 = null;
					 _link2 = null;
					 _link3 = null;
					 _thisLinkedListNode.Value = null;
				}
			}
			public void ResetLink(Link link, Link newLink)
			{
				if(link == Link1) Link1 = newLink;
				else if(link == Link2) Link2 = newLink;
				else if(link == Link3) Link3 = newLink;
			}
			public Vector3 Normal
			{
				get
				{
					return (_link2.Point.Position - _link1.Point.Position).Cross(_link3.Point.Position - _link1.Point.Position).normalized;
				}
			}
		}
		private static Point[] Import(LinkedList<Triangle> triangles, Mesh m)
		{
			Point.Init();
			
			Vector3[] vertices = m.vertices;
			Vector3[] normals = m.normals;
			Vector4[] tangents = m.tangents;
			Vector2[] uvs = m.uv;
			int[] triangleIndices = m.triangles;
			
			Point[] points = new Point[vertices.Length];
			
			for(int i = 0; i < vertices.Length; i++)
			{
				points[i] = Point.RequesPoint(vertices[i]);
			}
			
			for(int i = 0; i < triangleIndices.Length; i+=3)
			{
				int index1 = triangleIndices[i+0];
				int index2 = triangleIndices[i+1];
				int index3 = triangleIndices[i+2];
				
				Link l1 = points[index1].RequestLink(uvs[index1], normals[index1], tangents[index1]);
				Link l2 = points[index2].RequestLink(uvs[index2], normals[index2], tangents[index2]);
				Link l3 = points[index3].RequestLink(uvs[index3], normals[index3], tangents[index3]);
				new Triangle(l1, l2, l3, triangles);
			}
			return points;
		}
		private static void Export(LinkedList<Triangle> triangles, Mesh m)
		{
			LinkedList<Vector3> vertices = new LinkedList<Vector3>();
			LinkedList<Vector3> normals = new LinkedList<Vector3>();
			LinkedList<Vector4> tangents = new LinkedList<Vector4>();
			LinkedList<Vector2> uvs = new LinkedList<Vector2>();
			LinkedList<int> triangleIndices = new LinkedList<int>();
			
			int indexCounter = 0;
			
			foreach(Triangle t in triangles)
			{
				if(!t.Link1.HasBeenIndexed)
				{
					vertices.AddLast(t.Link1.Point.Position);
					uvs.AddLast(t.Link1.UV);
					normals.AddLast(t.Link1.Normal);
					tangents.AddLast(t.Link1.Tangent);
					t.Link1.Index = indexCounter++;
				}
				if(!t.Link2.HasBeenIndexed)
				{
					vertices.AddLast(t.Link2.Point.Position);
					uvs.AddLast(t.Link2.UV);
					normals.AddLast(t.Link2.Normal);
					tangents.AddLast(t.Link2.Tangent);
					t.Link2.Index = indexCounter++;
				}
				if(!t.Link3.HasBeenIndexed)
				{
					vertices.AddLast(t.Link3.Point.Position);
					uvs.AddLast(t.Link3.UV);
					normals.AddLast(t.Link3.Normal);
					tangents.AddLast(t.Link3.Tangent);
					t.Link3.Index = indexCounter++;
				}
				triangleIndices.AddLast(t.Link1.Index);
				triangleIndices.AddLast(t.Link2.Index);
				triangleIndices.AddLast(t.Link3.Index);
			}
			
			m.Clear();
			
			m.vertices = vertices.ToArray();
			m.uv = uvs.ToArray();
			m.normals = normals.ToArray();
			m.tangents = tangents.ToArray();
			m.triangles = triangleIndices.ToArray();
			
			m.RecalculateBounds();
		}
		private static void RelayModifyShapeFast(Point[] points, Func<Vector3, Vector3> func)
		{
			foreach(Point p in points)
			{
				if(!p.HasBeenVisited) p.Position = func( p.Position );
			}
		}
		private static void RelayModifyShape(Point[] points, Func<VertexPoint, Vector3> func)
		{
			foreach(Point p in points)
			{
				if(!p.HasBeenVisited)
				{
					Link anyLink = p.AnyLink;
					if(anyLink != null) p.Position = func( (VertexPoint)anyLink );
				}
			}
		}
		private static void RelayModify(LinkedList<Triangle> triangles, Action<VertexPoint> func)
		{
			foreach(Triangle t in triangles)
			{
				if(!t.Link1.HasBeenVisited) t.Link1.Modify(func);
				if(!t.Link2.HasBeenVisited) t.Link2.Modify(func);
				if(!t.Link3.HasBeenVisited) t.Link3.Modify(func);
			}
		}
		private static void Reduce(Point[] points, float amount, bool convex)
		{
			foreach(Point p in points)
			{
				if(!p.HasBeenVisited) p.ForEachLink(link => Reduce(link, amount, convex));
			}
		}
		private static void Reduce(Link link, float amount, bool convex)
		{
			Vector3 linkPos = link.Point.Position;
			float threshold = convex ? -0.001F : 1F - amount;
			
			var links = link.Triangles.SelectMany<Triangle, Link>(x => x.Links);
			float best = amount;
			Point bestTarget = null;
			foreach(Link a in links)
			{
				Vector3 aNormal = a.Point.Position.DirectionTowards(linkPos);
				foreach(Link b in links)
				{
					Vector3 bNormal = linkPos.DirectionTowards(b.Point.Position);
					float score = aNormal.Dot(bNormal);
					if(score > best)
					{
						Point target = null;
						float aDist = aNormal.Dot(linkPos - a.Point.Position);
						float bDist = bNormal.Dot(b.Point.Position - linkPos);
						if(aDist < bDist)
							target = a.Point;
						else
							target = b.Point;
						
						Vector3 edgeDir = linkPos.DirectionTowards(target.Position);
						foreach(Triangle tr in link.Triangles)
						{
							if(tr.Normal.Dot(edgeDir) < threshold)//if 'ok-ness' < 'ok-threshold'
							{
								target = null;//cancel
								break;
							}
						}
						if(target == null)
							continue;
							
						best = score;
						bestTarget = target;
					}
				}
			}
			if(bestTarget != null)
				link.Point.CollapseWith(bestTarget);
		}
	}
}

